<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 
         * 最长回文子序列
         * 输入：s = "bbbab"
         * 输出：4 
         * 解释：一个可能的最长回文子序列为 "bbbb" 。
         * 
         * 输入：s = "cbbd"
         * 输出：2
         * 解释：一个可能的最长回文子序列为 "bb" 。
         * 
         * dp[i][j]，从i->j之间的最长回文子序列的长度
         * 分析：转化为最长公共子序列的问题，求出s的倒序s2，然后求s和s2的最长公共子序列，bbbab是给定的s，得到s2是babbb，求bbbab和babbb的最长公共子序列是bbbb，=> 回文子序列正和反读起来是一样的，所以倒序能行
         * 
        */
        /* 
            时间：O(n * n)
            空间：O(n * n)
        */
        // 动态规划
        var longestPalindromeSubseq = function(s) {
            let s2 = s.split('').reverse().join('')
            let len1 = s.length;
            let len2 = s2.length;
            let dp = new Array(len1 + 1).fill(0).map(() => new Array(len2 + 1).fill(0));
            // dp[i][0]和dp[0][j]都是0，因为text1从0 -> i-1字符串和''空字符串的公共子序列都是0，dp[i][0]的j是0，意味是这个比较的text2的就是空字符串，思考dp数组的定义就能够得出
            // 需要双重for循环
            for (let i = 1; i <= len1; i++) {
                // j需要倒序,倒序的原因是：1. dp[j]需要从上一轮的dp[j - 1]推导出来 2. 正序，可能dp[j - 1]在这一轮又被用了一次
                for (let j = 1; j <= len2; j++) {
                    if (s[i - 1] === s2[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1
                    } else {
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i -1][j])
                    }
                }
            }
            return dp[len1][len2]
        };
        console.log(longestPalindromeSubseq('abc'));
        console.log(longestPalindromeSubseq('aaa'));
    </script>
</body>

</html>